package com.ryujung.linked_list.leetCode_1019;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/*
Next Greater Node In Linked List

We are given a linked list with head as the first node.  
Let's number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) 
is the node_j.val such that j > i, node_j.val > node_i.val, 
and j is the smallest possible choice.  If such a j does not exist, 
the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] 
represent the serialization of a linked list with a head node value of 2, 
second node value of 1, and third node value of 5.
*/
/**
 * 思路:贪心算法的链表版本
 * 
 */
public class Solution {
    public int[] nextLargerNodes(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ArrayList<Integer> al = new ArrayList<Integer>();

        //将链表中的值存到list中,方便操作
        while(head!=null){
            al.add(head.val);
            head = head.next;
        }

        int[] res = new int[al.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = al.get(i);
        }
        return null;

    }
}

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}